package zoran.wang.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 多叉树的遍历
 *
 * @author wangzhuo
 * @time 2025-04-12-14:53
 */
public class MultiwayTreeTraversal {

    // 递归遍历
    public void traverse(Node root) {

        if (root == null) return;

        System.out.println(root.val);

        for (Node child : root.children) {
            traverse(child);
        }
    }

    public LinkedList<Node> path = new LinkedList<>();

    //遍历路径，寻找根节点到目标节点的路径，如果要重复使用，请重置 path 缓存
    public void traversePath(Node root, Node targetNode) {

        // base case
        if (root == null) return;

        // 前序位置
        path.add(root);

        // 如果找到了目标节点，则输出路径
        if (root == targetNode) {
            System.out.println("find path:");
            for (Node node : path) {
                System.out.print(node.val + " ");
            }
        }


        // DFS 遍历模板
        for (Node child : root.children) {
            traversePath(child, targetNode);
        }

        // 后序位置
        path.removeLast();
    }

    // 层序遍历
    public void levelOrderTraverse(Node root) {

        // 借助队列
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        // 根节点深度
        int depth = 1;

        // 遍历
        while (!q.isEmpty()) {
            int levelSize = q.size();

            // ************** 遍历一层 start **************
            for (int i = 0; i < levelSize; i++) {
                Node node = q.poll();
                System.out.println(node.val + " in level " + depth);

                // 放入其所有子节点
                for (Node child : node.children) {
                    if (child != null) q.offer(child);
                }
            }
            // ************** 遍历一层 end **************
            depth++;
        }
    }
}
